The subject invention relates to encryption of information using public key encryption technology. (By xe2x80x9cpublic keyxe2x80x9d encryption herein is meant encryption technology which uses pairs of keys: a public key, which is published or made publicly known; and a corresponding private key, kept secret by a user.) More particularly it relates to the certification of public keys by a plurality of certifying authorities.
Using public key encryption anyone can encrypt a message with a public key and have assurance that only a user (i.e. a party having the corresponding private key) can decrypt it, and a user can xe2x80x9csignxe2x80x9d a message using a private key and anyone can use the corresponding public key to ascertain if the message originated with the user. (A message is xe2x80x9csignedxe2x80x9d by deriving encrypted information in a known manner from the message.)
Because public keys can be distributed so widely, it will in general be the case that persons communicating with users of public key systems will not be in direct contact with the users and will not be able to directly determine the identity and/or characteristics of the putative users of a public key system. For example a vendor who receives a purchase order signed by the user of a public key which is purportedly that of an authorized agent of the buyer may need to know, but have no way of directly determining, the actual authority of the user. Similarly proof of payment systems, in particular postage meters, which generate indicia encrypted using public key systems as proof of payment have recently been developed by the assignee of the present application and others; and, given the hundreds of thousands of postage meters in service, it is clear that the postal services will face a severe problem in assuring that indicia purportedly generated by a meter corresponding to a particular public key is in fact generated by an authorized postage meter.
To overcome the difficulties inherent in authenticating public keys numerous schemes for issuing certificates for public keys have been proposed. In such schemes, a trusted third party (hereinafter sometimes a xe2x80x9ccertifying authorityxe2x80x9d) provides parties who wish to communicate with a user with a certificate containing the user""s public key, the certificate serving to evidence the third party""s assurances as to the identity or characteristics of the user. In the simplest case such certificates are no more than entries in a directory delivered through a secure channel. More generally the certifying authority will use an encryption technology to deliver the certificate.
In U.S. Pat. No. 4,853,961; for: xe2x80x9cReliable Document Authentication Systemxe2x80x9d; to: Pastor, a public key for a postage meter is encrypted with a third party""s private key and included in the meter indicia. The postal service uses the third party""s public key to recover the meter public key and decrypt the encrypted message which serves to validate the indicia.
In U.S. Pat. No. 5,661,803; for: xe2x80x9cMethod of Token Verification in a Key Management Systemxe2x80x9d; to: Cordery et al., a method of token verification in a key management system is disclosed.
In U.S. Pat. No. 5,680,456; for: xe2x80x9cMethod of Manufacturing Generic Meters in a Key Management Systemxe2x80x9d; to: Baker et al., a method for manufacturing transaction evidencing devices such as postage meters includes the steps of generating a master key in a logical security domain of a key management system and installing the master key in a postage meter.
In U.S. Pat. No. 5,742,682; for: xe2x80x9cMethod of Manufacturing Secure Boxes in a Key Management Systemxe2x80x9d; to: Baker et al., a method of manufacturing a secure box in a key management system is taught.
In U.S. Pat. No. 5,805,701; for: xe2x80x9cEnhanced Encryption Control System for a Mail Processing System Having Data Center Verificationxe2x80x9d; to: Ryan, Jr., a key control system comprising generation of a first set of master keys and assigning the keys to a corresponding plurality of postage meters is taught.
In U.S. application Ser. No. 08/133,416; by: Kim et al.; filed Oct. 8, 1993, a key control system comprising generation of a first set of master keys and assigning the keys to a corresponding plurality of postage meters is taught. Keys may be changed by entry of a second key via encryption with a first key.
In U.S. application Ser. No. 08/772,739; by: Cordery; filed Dec. 23, 1996, a method for controlling keys used in the verification of encoded information generated by a transaction evidencing device and printed on a document is taught.
While the above methods are successful in achieving their intended purpose they are disadvantageous in that they are computationally complex, may produce certificates which are large and inflexible, and may require special hardware.
The following references contain information useful to a general understanding of elliptic curve encryption and certification of public keys.
Secure Hash Standardxe2x80x94FIPS PUB 180-1,xe2x80x9d Apr. 17, 1995.
Digital Signature Standardxe2x80x94FIPS PUB 186,xe2x80x9d May 19, 1994 and Change 1, Dec. 30, 1996.
ANSI X9.62, Elliptic Curve Digital Signature Algorithm Standard (ECDSA), Working Draft, Jan. 15, 1997.
ISO/IEC 9594-8 (1995). Information Technologyxe2x80x94Open Systems Interconnectionxe2x80x94The Directory: Authentication Framework.xe2x80x9d
PKCS #10: Certification Request Syntax Standard, An RSA Laboratories Technical Note,xe2x80x9d Version 1.0, December 1993.
Another method of key certification based upon elliptic curve public key encryption technology has been developed by the Certicom Corporation. (The use of elliptic curve encryption technology is known and a more detailed description of its use, beyond what is given below in the context of certification of public keys, is not required for an understanding of the subject invention.)
Elliptic curve encryption is an example of a cryptographic algorithm based on application of an binary additive operator to points in a finite group. In elliptic curve encryption a finite group of points [P] of order n is defined on an elliptic curve. A binary additive operator [+] (hereinafter sometimes xe2x80x9cpoint additionxe2x80x9d) is defined on the group [P] such that P[+]Pxe2x80x2 is a point in [P]. A more detailed, graphical description of point addition is shown in FIG. 1. As is known to those skilled in the cryptographic art, disjoint curve 10 has the general form y2=x3+ax+b defined over the finite Galois field GF(pm) where p is a prime number other than 2 and m is an integer. Over the Galois field GF(2m) the curve has the form y2+xy=x3+ax+b. It can be shown that groups of discrete points [P] of order n can be defined on curve 10, where n is preferably a number on the order of at least 50 decimal digits in order to provide sufficient security for encrypted information.
As is seen in FIG. 1 curve 10 is symmetric about the x axis so that for any point (x,y) on curve 10 its reflection around the x axis R(x,y)=(x,xe2x88x92y) is also on curve 10.
For two points P,Pxe2x80x2 in [P] it can be show that there exists a unique point R(P[+]Pxe2x80x2) which is a third point common to straight line 12 defined by P and Pxe2x80x2 and curve 10. P[+]Pxe2x80x2 is defined as R(R(P[+]Pxe2x80x2)).
FIG. 2 shows the special case for computation of P[+]P. Straight line 14 is defined as tangent to the closed portion of curve 10 and intersecting point P, and R(P[+]P) is defined as the second point common to line 14 and curve 10.
A second operation K*P (herein after sometimes xe2x80x9cpoint multiplicationxe2x80x9d) is defined as the application of [+] to K copies of a point P. FIG. 3 geometrically illustrates computation of 5*P by successive computation of the points P[+]P=2*P, 2*P[+]2*P=4*P, 4*P[+]P=5*P. Point multiplication is the basic operation underlying elliptic curve encryption and has the property that computation of K from knowledge of the group [P], a particular point P, and K*P is hard.
By xe2x80x9chardxe2x80x9d as used herein in regard to computation is meant a computation wherein the time required increases faster than the order of the operands (log n), and preferably exponentially or faster with log n. This means that where K is of order n, the order of [P], and n is chosen large enough the cost, in time or money, of computing K from knowledge of the definition of [P], P, and K*P can be made arbitrarily large while the cost of other computations relating to encryption or decryption remains relatively low and practicable. Of course those skilled in the encryption art will recognize that, even though encryption and decryption can in principle be carried out by manual computation, the possibly of an attack on an encryption scheme using modern computer technology requires that, in practice, the order n be so great that even the relatively easy computations must be carried out by automated encryption stations; e.g. special purpose, or specially programmed general purpose, digital processing systems.
Point multiplication has been described in terms of the group represented by point addition on a discrete elliptic curve. In other embodiments the subject invention can be implemented using any group representation where determining K is hard given the point P and the point formed by combining K copies of point P by repeated application of the group additive point operation. Accordingly, unless otherwise stated the terms xe2x80x9cpoint Pxe2x80x9d and xe2x80x9cgroup [P]xe2x80x9d as used herein are intended to include any elements, e.g. integers, functions, permutations, etc., as well as spatial points, for which a binary operation and corresponding group having the necessary properties as described above can be defined.
In elliptic curve encryption a user U has a private key KeyU and a corresponding public key KeyU*P; where P is a published or publicly known point in [P]. To generate a certified public key in accordance with the above mentioned Certicom encryption scheme user U (i.e. a station operated by user U) generates and keeps secret a random number rU; and computes and sends to a certifying authority CA the point rU*P. Certifying authority CA has a private KeyCA and a public key KeyCA*P. Upon receipt of rU*P the CA generates a random number rCA and computes and publishes a certificate including a point, rU*P[+]rCA*P, wherein rCA is a random number generated by the CA (i.e. by the CA station). Authority CA, which is presumed to have the capability to directly determine the identity or characteristics of user U, also generates information IDU about U and includes IDU in the certificate. Certifying Authority CA then returns an integer derived from the CA""s private key and the certificate to the user station which uses that integer to compute key KeyU in such a manner that a party communicating with user U can compute KeyU*P from the certificate and the certifying authority""s public key KeyCA; providing evidence that the certifying authority has linked user U, KeyU, and IDU. The user does not know rCA and the CA does not know rU. With this procedure, only the user knows KeyU and only the CA could link IDU to the CA public key.
The above described certification scheme is believed to be advantageous in that it is computationally simpler, and produces smaller certificates. However it does not address the situation where a user may act in one of a plurality of capacities or wish to clearly evidence that he or she is asserting only a selected subset of the rights and parties communicating with the user may need assurance that the user possess at least the rights or authority asserted. For example, during negotiations a party may wish to sign messages as evidence of his or her identity, and only when making or accepting an offer may wish to sign a message so as to evidence authority to act as agent for one or more principles. Such a capability would be particularly useful where some of a group of principles elect to opt out of a deal at the last moment. The agent could then make or accept a binding offer; signing it in a manner which would evidence that the agent acted only on behalf of those principles who elected to accept the deal.
The above object is achieved and the disadvantages of the prior art are overcome in accordance with the subject invention by a method and apparatus which provide the user with a collection of certified rights, each with its own certificate. The certificate for each right has its own validity conditions such as validity period and revocation status and each right can be certified by a separate authority. The user constructs a private key associated with any subset of his collection of certified rights, and thereby can sign a message with a private key which evidences only the rights asserted for the message.
In accordance with one aspect of the invention information is distributed among, a plurality of stations, one of the stations being a user station operated by a user U to generate a plurality of private encryption keys KeyU,i and others of the stations being certifying stations operated by a plurality of certifying authorities for publishing related information, the related information identifying particular rights certified to the user U, so that a corresponding public key KeyU ,sum(i)*P of user U can be determined by a party communicating with user U from the published related information with assurance that at least rights asserted by user U have been certified by corresponding ones of the certifying authorities CA, but the party cannot claim that other rights were asserted. The method of distribution includes: a) defining a finite group [P] with a binary operation [+] and publishing a particular point P in the group; b) defining and publishing a binary operation K*p, where K is an integer and p is a point in the group, such that K*p is a point in the group computed by applying the operation[+] to K copies of point p, and computation of K from knowledge of the definition of group [P], point p, and K*p is hard; c) controlling each of the certifying stations to publish a certificate CERTU,i for said user U, wherein;
CERTU,i=(rU,i+rCAi)*P; and wherein
rU,i is a random integer known only to said user U and rCAi is a random integer generated by an ith one of said certifying stations; d) controlling each of the certifying stations to publish a message Mi, message Mi identifying particular rights certified to user U by an ith one of the certifying stations; e) controlling each of the certifying stations to generate an integer Ii, and send Ii to the user station, wherein;
Ii=rCAi+H(Mi)KeyCAi; and wherein
H(Mi) is an integer derived from the message Mi in accordance with a publicly known algorithm H, and rCAi is one of the random integers generated by, and KeyCAi is a private key of, an ith one of the certifying stations; f) publishing a public key KeyCAi*P for each of the certifying authorities CA; and g) controlling said user station to compute a plurality of private keys KeyU,i, wherein
KeyU,i=rU,i+Ii=rU,i+rCAi+H(Mi)KeyCAi 
whereby h) user U can generate a private key KeyU,sum(i) to communicate while asserting only a selected subset of rights
KeyU,sum(i)=sum(KeyU,i)=sum(rU,i+rCAi+H(Mi)KeyCAi)
summed over asserted rights; and i) the communicating party can compute said user""s public key KeyU,sum(i)*P as
KeyU,sum(i)*P=sum[+](CERTU,i[+]H(Mi)KeyCAi*P)=sum[+]((rU,i+rCAi)*P+H(Mi)KeyCAi*P)=sum(rU,i+rCAi+H(Mi)KeyCAi)*P
from knowledge of H, messages Mi, [P], said public keys KeyCAi*P, and certificates CERTU,i.
In accordance with another aspect of the invention the publicly known manner for deriving an integer from the published information comprises applying a hashing function to the messages Mi.
In accordance with another aspect of the invention at least one of the messages Miincludes information identifying or characterizing user U.
In accordance with another aspect of the invention at least one of the messages Mi includes information identifying or characterizing user U.
In accordance with another aspect of the invention at least one of the particular rights is certified to user U by a plurality of certifying authorities operating a corresponding plurality of certifying stations.
In accordance with another aspect of the invention the group [P] is defined on an elliptic curve.
In accordance with another aspect of the invention messages Mi include information tying user U""s public key KeyU,i*P to information IDRU,i which identifies particular rights which can be certified by an ith one of the certifying authorities CA.
In accordance with still another aspect of the invention data processing apparatus includes a programmable processor programmed to control said apparatus as a user station used by user U to generate a plurality of private encryption keys KeyU,i, said user station communicating with a plurality of certifying stations, each of the certifying stations being controlled to publish related information, the related information identifying particular rights certified to user U, so that a corresponding public key KeyU,sum(i)*P of said user U can be determined by a party communicating with said user U from the published related information with assurance that at least rights asserted by user U have been certified by corresponding ones of the certifying authorities CA, but cannot claim that other rights were asserted, the related information including certificates CERTU,i for user U, wherein CERTU,i is (rU,i+rCAi)*P, wherein P is a published point in a group [P], and wherein rU,i is a random integer known only to user U and rCAi is a random integer generated by an ith one of the certifying stations; the processor controlling the apparatus to: a) transmit a point rU,i*P in said group [P] to at least an ith one of said certifying stations to request particular rights certified by said ith certifying station; b) receive at least one encrypted integer Ii from the ith certifying station, wherein;
Ii=rCai+H(Mi)KeyCAi; and wherein
H(Mi) is an integer derived from said message Mi in accordance with a publicly known algorithm H, and rCAi is a random integer generated by, and KeyCAi is a private key of the ith certifying station; c) generate at least one private key KeyU,i as:
KeyU,i=rU,i+Ii=rU,i+rCAi+H(Mi)KeyCAi; 
whereby d) the user can generate a private key KeyU,sum(i) to communicate while asserting only a selected subset of rights
KeyU,sum(i)=sum(KeyU,i)=sum(rU,i+rCAi+H(Mi)KeyCAi)
summed over asserted rights; and e) the communicating party can compute the user""s public key KeyU,sum(i)*P as
KeyU,sum(i)*P=sum[+](CERTU,i[+]H(Mi)KeyCAi*P)=sum[+]((rU,i+rCAi)*P+H(Mi)KeyCAi*P)=sum(rU,i+rU,i+H(Mi)KeyCAi)*P
from knowledge of H, messages Mi, [P], public keys KeyCAi*P, and certificates CERTU,i.
In accordance with still another aspect of the invention portable data storage media store signals representative of program code the code readable by a data processing apparatus to control the apparatus to operate as a user station used by a user U to generate a plurality of private encryption keys KeyU,i, the user station communicating with a plurality of certifying stations, each of the certifying stations being controlled to publish related information, the related information identifying particular rights certified to the user U, so that a corresponding public key Keysum(i)*P of user U can be determined by a party communicating with user U from the published related information with assurance that at least rights asserted by user U have been certified by a corresponding one of the certifying authorities CA, but cannot claim that other rights were asserted, the related information including a certificates CERTU,i for said user U, wherein CERTU,i is (rU,i+rCAi)*P, wherein P is a published point in a group [P], and wherein rU,i is a random integer known only to said user U and rCai is a random integer generated by an ith one of the certifying stations.
In accordance with still another aspect of the invention a method for certification of a public key of a user by a plurality of certifying authorities, each of said certifying authorities having a published public key and a corresponding private key, includes the steps of: a) each of the certifying authorities providing the user with an integer, each of the integers being a first function of one of the private keys for a corresponding one of said authorities; b) the user computing a plurality of private keys, each of the private keys being a second function of one of the integers; c) each of the certifying authorities publishing related information, the related information identifying a particular right certified to the user by a corresponding one of the authorities; and d) the user computing a summed private key corresponding to a subset of asserted rights by arithmetic summation of selected ones of the plurality of private keys; wherein e) the first function, the second function and the published related information are chosen so that a party communicating with the user can compute a user public key, corresponding to said summed private key, by operating on the published related information with a point summation of said published public keys of the authorities.
In accordance with still yet another aspect of the invention a party communicating with user U can determine a public key KeyU,sum(i)*P of a user""s encryption station with assurance that at least rights asserted by said user U have been certified by corresponding ones of a plurality of certifying authorities CA, but cannot claim that other rights were asserted. The method includes the steps of: a) obtaining a certificates CERTU,i corresponding to the rights asserted by the user U, wherein;
CERTU,i=(rU,i+sum(rCAi))*P; and wherein
rU,i is a random integer known only to user U and sum(rCAi) is a sum of a plurality of random integers rCAi, summed over certifying stations corresponding to said rights asserted by user U, an ith one of the certifying stations generating an ith one of the random integers rCAi; b) obtaining messages Mi, each of the messages Mi being published by a one of the certifying stations corresponding to the rights asserted by user U; c) computing a hash H(Mi) of each of the messages Mi in accordance with a predetermined hashing function H; d) obtaining a plurality of public keys KeyCAi*P for the plurality of corresponding certifying authorities CA, an ith one of said authorities having an ith one of said keys KeyCAi; and e) computing user U""s public key KeyU,sum(i)*P, summed over asserted rights, as
KeyU,sum(i)*P=sum[+](CERTU,i[+]H(Mi)KeyCAi*P)=sum[+]((rU,i+rCAi)*P[+]H(Mi)KeyCAi*P)=sum(rU,i+rCAi+H(Mi)KeyCAi)*P;
wherein f) a binary operation [+] is defined on a finite group [P] having a published particular point P; and g) K*p, is a second binary operation defined on the group [P], where K is an integer and p is a point in the group, such that K*p, is a point in the group computed by applying the operation [+] to K copies of point p, and computation of K from knowledge of the definition of said group [P], the point p, and K*p is hard.